package week_six;

public class ClimbingStairs_70 {
    //DP，动规.
    //阶段1-n, 状态 f(n) = f(n-1) + f(n-2)
    //重叠子问题 f(n)， 决策 影响n的只有n-1和n-2的状态。
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int f1 = 1, f2 = 2;
        int steps = 0;
        for (int i = 3; i <= n; i++) {
            steps = f1 + f2;
            f1 = f2;
            f2 = steps;
        }
        return steps;
    }
}
